/*
Problem Description
很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。
这让很多学生很反感。

不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。
Input
本题目包含多组测试，请处理到文件结束。
在每个测试的第一行，有两个正整数 N 和 M ( 0<N<=200000,0<M<5000 )，分别代表学生的数目和操作的数目。
学生ID编号分别从1编到N。
第二行包含N个整数，代表这N个学生的初始成绩，其中第i个数代表ID为i的学生的成绩。
接下来有M行。每一行有一个字符 C (只取'Q'或'U') ，和两个正整数A，B。
当C为'Q'的时候，表示这是一条询问操作，它询问ID从A到B(包括A,B)的学生当中，成绩最高的是多少。
当C为'U'的时候，表示这是一条更新操作，要求把ID为A的学生的成绩更改为B。
Output
对于每一次询问操作，在一行里面输出最高成绩。
Sample Input
5 6
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 2 9
Q 1 5
Sample Output
5
6
5
9
 */
package com.yuan.algorithms.team20150724;

import java.io.BufferedInputStream;
import java.util.Scanner;

/**
 * @author YouYuan
 * @author E-mail:1265161633@qq.com
 * @version 创建时间：2015年8月2日 下午4:31:18
 * @version 说明:利用线段树存储区间中的最大分数，便于查询。 用二叉树存储超过内存限制，使用数组存储更为高效。
 */

class IntervalTree {
	
	private class TreeNode {
		public TreeNode L, R;//左节点、右节点
		public int valL, valR;//左区间、右区间
		public double maxScore;//最大分数
		
	}
	
	public TreeNode root;//线段树根节点
	
	public IntervalTree() {
		root = new TreeNode();
	}
	
	/**
	 * 构建线段树
	 * @param node 当前节点
	 * @param data 数据
	 * @param l 左区间
	 * @param r 右区间
	 * @return
	 */
	public TreeNode build(TreeNode node, int[] data, int l, int r) {
		node.valL = l;
		node.valR = r;
		if (l == r) {
			node.maxScore = data[l];
			return node;
		} else {
			int mid = (l+r) >> 1;
			node.L = build(new TreeNode(), data, l, mid);
			node.R = build(new TreeNode(), data, mid+1, r);
			node.maxScore = Math.max(node.L.maxScore, node.R.maxScore);
		}
		return node;
	}
	
	/**
	 * 查找线段树中的区间最大值
	 * @param node 根节点
	 * @param l 左区间
	 * @param r 右区间
	 * @return
	 */
	public double search(TreeNode node, int l, int r) {
		if (l==node.valL && r==node.valR) {
			return node.maxScore;
		} else {
			int mid = (node.valL + node.valR)>>1;
			if (r<=mid) {//判断查询的范围是否全部在树的左子树
				return search(node.L, l, r);
			} else if (l>mid) {//判断查询的范围是否全部在树的右子树
				return search(node.R, l, r);
			} else {
				//查询区间一部分在左子树，一部分在右子树的情况
				return Math.max(search(node.L, l, mid), search(node.R, mid+1, r));
			}
		}
	}
	
	/**
	 * 更新线段树中的值
	 * @param node
	 * @param index
	 * @param value
	 * @return
	 */
	public double update(TreeNode node, int index, double value) {
		if (index == node.valL && index==node.valR) {
			//到达叶子节点，更新节点最大分数
			return node.maxScore = value;
		}
		int mid = (node.valL + node.valR)>>1;
		double temp = 0;
		if (index <= mid) {
			temp = update(node.L, index, value);
		} else {
			temp = update(node.R, index, value);
		}
		return node.maxScore = Math.max(temp, node.maxScore);
	}
	
}

public class 线段树_区间查询最大分数_二叉树实现 {

	static int[] score;
	public static void main(String[] args) {
//		Scanner sc = new Scanner(System.in);
		Scanner sc = new Scanner(new BufferedInputStream(System.in));
		while(sc.hasNext()) {
			int n = sc.nextInt();
			int m = sc.nextInt();
			score = new int[n+1];
			for (int i = 1; i <= n; i++) {
				score[i] = sc.nextInt();
			}
			IntervalTree tree = new IntervalTree();
			tree.build(tree.root, score, 1, n);
			while(--m>=0) {
				char k = sc.next().charAt(0);
				int a = sc.nextInt();
				int b = sc.nextInt();
				if (k=='U') {
					tree.update(tree.root, a, b);
				} else {
					double rs = tree.search(tree.root, a, b);
					System.out.println((int)rs);
				}
			}
		}
	}

}
